package javafoundation;


import java.util.*;


public class ArrayBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T>
{
    private static final int DEFAULT_CAPACITY = 50;

    protected int count;
    protected T[] tree;
    protected int modCount;

    public ArrayBinaryTree()
    {
        count = 0;
        tree = (T[]) new Object[DEFAULT_CAPACITY];
    }

    public ArrayBinaryTree(T element)
    {
        count = 1;
        tree = (T[]) new Object[DEFAULT_CAPACITY];
        tree[0] = element;
    }

    protected void expandCapacity()
    {
        tree = Arrays.copyOf(tree, tree.length * 2);
    }

    public T getRootElement() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayBinaryTree");

        return tree[0];
    }

    public boolean isEmpty()
    {
        return (count == 0);
    }

    public int size()
    {
        return count;
    }

    public boolean contains(T targetElement)
    {
        T temp;
        boolean found = false;

        try
        {
            temp = find(targetElement);
            found = true;
        }
        catch (Exception | javafoundation.ElementNotFoundException ElementNotFoundException)
        {
            found = false;
        }

        return found;
    }

    public T find(T targetElement) throws ElementNotFoundException
    {
        T temp = null;
        boolean found = false;

        for (int i = 0; i < tree.length && !found; i++)
            if (tree[i] != null)
                if (targetElement.equals(tree[i]))
                {
                    found = true;
                    temp = tree[i];
                }

        if (!found)
            throw new ElementNotFoundException("ArrayBinaryTree");

        return temp;
    }


    public String toString()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        inOrder(0, tempList);

        return tempList.toString();
    }

    public Iterator<T> iterator()
    {
        return this.iteratorInOrder();
    }

    public Iterator<T> iteratorInOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        inOrder(0, tempList);

        return new TreeIterator(tempList.iterator());
    }

    protected void inOrder(int node, ArrayUnorderedList<T> tempList)
    {
        if (node < tree.length)
            if (tree[node] != null)
            {
                inOrder(node * 2 + 1, tempList);
                tempList.addToRear(tree[node]);
                inOrder((node + 1) * 2, tempList);
            }
    }

    public Iterator<T> iteratorPreOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(0, tempList);

        return new TreeIterator(tempList.iterator());
    }

    protected void preOrder(int node, ArrayUnorderedList<T> tempList)
    {
        if (node < tree.length)
            if (tree[node] != null)
            {
                tempList.addToRear(tree[node]);
                preOrder(node * 2 + 1, tempList);
                preOrder((node + 1) * 2, tempList);
            }
    }

    public Iterator<T> iteratorPostOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        postOrder(0, tempList);

        return new TreeIterator(tempList.iterator());
    }

    protected void postOrder(int node, ArrayUnorderedList<T> tempList)
    {
        if (node < tree.length)
            if (tree[node] != null)
            {
                postOrder(node * 2 + 1, tempList);
                postOrder((node + 1) * 2, tempList);
                tempList.addToRear(tree[node]);
            }
    }

    public Iterator<T> iteratorLevelOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        int ct = 0;
        int i = 0;

        while (ct < count)
        {
            if (tree[i] != null)
            {
                tempList.addToRear(tree[i]);
                ct++;
            }
            i++;
        }

        return new TreeIterator(tempList.iterator());
    }

    private class TreeIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;

        public TreeIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }

        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }

        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }

        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
}


